#!/usr/bin/python
# Filename: NBTree.py

# node binary tree:
# binary tree without a root reference,
# there's only TreeNode class, without Tree class


class TreeNode:

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return (str(self.value))

    # the tree calling postorder_string won't be empty,
    # bcz when calling, this tree node must be already exist.
    def postorder_string(self):
        string = ''
        if self.left:
            string += self.left.postorder_string()
        if self.right:
            string += self.right.postorder_string()
        string += (str(self.value) + ", ")
        return (string)


def print_tree_postorder(tree):
    if tree:
        print_tree_postorder(tree.left)
        print_tree_postorder(tree.right)
        print tree,

def print_tree_indented(tree, level=0):
    if tree:
        print_tree_indented(tree.right, level+1)
        print '  '*level + str(tree)
        print_tree_indented(tree.left, level+1)
        
def get_token(token_list, expected):
    print "get_token", expected, ':', token_list
    if token_list[0] == expected:
        del token_list[0]
        return True
    else:
        return False

# find a number or a sub-tree in parenthesis,
# sub-tree is dealed as full token list.
def get_number(token_list):
    print "get_number:", token_list
    if get_token(token_list, '('):
        # get sub-expression
        x = get_sum(token_list)
        # remove the closing parenthesis
        get_token(token_list, ')')
        return x
    else:
        x = token_list[0]
        if type(x) != type(0):
            # this only happen when expression is not complete
            return None
        del token_list[0]
        return TreeNode(x)

# every time a number of ')' ends, get_product begin, until a serial of '*' ends.
def get_product(token_list):
    print "get_product", token_list
    a = get_number(token_list)
    if get_token(token_list, '*'):
        b = get_product(token_list)
        return TreeNode('*', a, b)
    else:
        return a

# every time a serial of '*' ends, get_sum begin, until a serial of '+' ends.
def get_sum(token_list):
    print "get_sum:", token_list
    a = get_product(token_list)
    if get_token(token_list, '+'):
        b = get_sum(token_list)
        return TreeNode('+', a, b)
    else:
        return a

if __name__ == "__main__":
    # token_list = [9, '*', '(', 11, '+', 5, ')', '+', 7, '+', 2, '!']
    token_list = [9, '*', 10, '+', 5, '+', 6, '!']    
    tree = get_sum(token_list)
    print_tree_indented(tree)
    print_tree_postorder(tree)
    e = tree.postorder_string()
    print '=', e
    # import Stack
    # print Stack.eval_postfix(e)

